//a mutable version of a string with a publicly accessable character array
//to save creating loads of new objects when doing IO
//it's basically a very simple wrapper around a character array that has a method to ensure
//that there is enough capacity in the array 
//NOTE: dont use get array to keep a copy of the array - modifications should be done 
//through this class - just use it to pass the array to IO classes
//JMR 9/3/2010

//NOTE: some work needs doing to this - not that fast + the code is a bit epic + not 
//very well documented - may be better to break the parsing stuff off into a different
//class which wraps around the data structure (although may result in more method calls)

//Ignore above! - wasted loads of time doing it and the extra method calls slowed down by
//approx 8*
//Now introduced buffered deletion instead

import java.io.Reader;
import java.io.IOException;
import java.util.NoSuchElementException;

public class CharString 
{
  private char array[];
  private int capacity = 10;
  private boolean usage_up_to_date = true;
  private int array_usage = 0;
  private boolean checked_for_next = false;
  private int checked_up_to = 0;
  private char delimiter = ' ';
  private CharString next;
  private boolean next_buffer_created = false;
  private int next_start = -1;
  private int next_end = -1;
  private boolean hasnext = false;
  private boolean lazy_mode = true;

  //variables to allow buffered deletion from the array:
  //start represents the starting index
  private int start = 0;
  //tolerance represents the furthest up the list that the start can be before triggering
  //a deletion
  private int tolerance = 0;

  public CharString ()
  {
    array = new char[capacity];
    tolerance = capacity/2;
  }

  public CharString (int capacity)
  {
    array = new char[capacity];
    tolerance = capacity/2;
  }

  //convience function to avoid writing same code over & over!
  //a function that given something readable will read it into a charstring until 
  //the source is exhausted 
  public static CharString read_into (Reader input) throws IOException
  {
    //read each file into a CharString
    CharString read_buffer = new CharString ();      
    int amount = 1000;
    int amount_read = 0;
    while (amount_read != -1){
      read_buffer.ensure_extra_capacity(amount);
      amount_read = input.read(read_buffer.get_array(),read_buffer.get_array_usage(),amount);
      
      if (amount_read != -1){
        read_buffer.return_array(amount_read);
      }
    }
    
    return read_buffer;
  }

  public char[] get_array ()
  {
    usage_up_to_date = false;
    return array;
  }

  //two version - one calcs usage other you specify
  public void return_array ()
  {
    check_usage();
  }

  public void return_array (int extra_usage)
  {
    array_usage += extra_usage;
    usage_up_to_date = true;
  }

  private void check_usage ()
  {
    array_usage = 0;
    for (int i = 0; i < capacity; i++){
      if (array[i] == 0){
        array_usage = i;
      }
    }
    usage_up_to_date = true;
  }

  public void ensure_total_capacity (int desired_capacity)
  {
    if (capacity < desired_capacity){
      enlarge(desired_capacity);
    }
  }

  public void ensure_extra_capacity (int extra_capacity)
  {
    while (extra_capacity > (capacity-array_usage)){
      enlarge();
    }
  }

  private void enlarge ()
  {
    char new_array [] = new char[capacity*2];
    for (int i = 0; i < array_usage; i++){
      new_array[i] = array[i];
    }
    array = new_array;
    capacity = capacity*2;
    tolerance = capacity/2;
  }

  private void enlarge (int new_capacity)
  {
    if (new_capacity <= capacity){
      enlarge();
    }

    else{
      char new_array [] = new char[new_capacity];
      for (int i = 0; i < array_usage; i++){
        new_array[i] = array[i];
      }      
      array = new_array;
      capacity = new_capacity;
    }
    tolerance = capacity/2;
  }

  //two string conversion methods - use the second to get a string version of the
  //character array - will likely change the first
  public String toString()
  {
    return String.format("CharString: capacity %d, usage %d, contents:\n%s",
                         capacity, array_usage ,new String(array));
  }

  //need a special method to return the string - just doing new String(array)
  //causes problems as empty capacity is not visible but added to string
  public String asString()
  {
    char trim_array[] = new char[array_usage];
    for (int i = start; i < array_usage; i++){
      trim_array[i] = array[i];
    }

    return new String(trim_array);
  }

  public void clear()
  {
    for (int i = 0; i < array_usage; i++){
      array[i] = 0;
    }
    array_usage = 0;

    usage_up_to_date = true;

    checked_for_next = false;
    start = 0;

    if (next_buffer_created){
      next_start = -1;
      next_end = -1;
      hasnext = false;
      next.clear();
      checked_up_to = 0;
    }

  } 

  public void add (char c)
  {
    try{
      array[array_usage] = c;
    }
    catch (ArrayIndexOutOfBoundsException e){
      enlarge();
      array[array_usage] = c;
    }
    array_usage += 1;

    changed();

  }

  //NOTE the string version of this function should generally not be used 
  //as strings are bad!
  public void add (String string)
  {
    for (int i = 0; i < string.length(); i++){
      add(string.charAt(i));
    }

    changed();
  }

  public void add (CharString input)
  {
    for (int i = 0; i < input.get_usage(); i++){
      add(input.get(i));
    }

    changed();
  }

  public void set (CharString input)
  {
    clear();
    int input_size = input.get_usage();
    if (capacity < input_size){
      ensure_total_capacity(input_size);
    }

    for (int i = 0; i < input_size; i++){
      array[i] = input.get(i);
    }
    array_usage = input_size;
    changed();
    checked_up_to = 0;
  }

  //again this is bad! so dont use it unless there is a good reason to!
  public void set (String string)
  {
    clear();
    add(string);
    changed();
    checked_up_to = 0;
  }

  public char get (int i)
  {
    return array[i];
  }

  public int get_usage()
  {
    return array_usage;
  }

  //in this implementation this works the same as above
  public int get_array_usage()
  {
   return get_usage();
  }

  //method to get rid of characters from array
  //note that the position provided includes that character
  //so doing trim_to_point(0) would get rid of the first character

  //NOTE this method probably slows things down a lot to improve speed
  //may either need to buffer this, forget about removing tokens or
  //have some more complicated kindof data structure to allow for quick deletions from the 
  //front + quick random access(possible like golf stuff)
  private void trim_to_point(int position)
  {

    if (position >= tolerance){
      for (int i = 0; i < array_usage; i++){
        try{
          array[i] = array[(i+1+position)];
        }
        catch (ArrayIndexOutOfBoundsException e){
          array[i] = 0;
        }
      }
      array_usage -= (position+1);

      checked_up_to -= (position+1);
      if (checked_up_to < 0){
        checked_up_to = 0;
      }
      start = 0;
    }
    else{
      start = position+1;
      checked_up_to = start;
    }
  }

  private void trim_from_point (int position)
  {
    for (int i = position; i < array_usage; i++){
      array[i] = 0;
    }

    array_usage = position;  

    if (checked_up_to > array_usage){
      checked_up_to = array_usage;
    }  

  }

  public void trim_whitespace ()
  {
    boolean other_found = false;
    int start_position = -1;
    int end_position = -1;
    for (int i = start; i < array_usage; i++){
      char c = array[i];
      if (!(Character.isWhitespace(c))){
        start_position = i-1;
        break;
      }
    }

    for(int i = array_usage-1; i >= start; i--){
      char c = array[i];
      if (!(Character.isWhitespace(c))){
        end_position = i+1;
        break;
      }
    }

    //trim from end first to save work
    if (end_position == -1){
      trim_from_point(0);
    }
    else if (end_position == array_usage){

    }
    else{
      trim_from_point(end_position);
    }

    //then trim from front
    if (start_position == -1){
      //note that this represents 2 cases - either it was all whitespace or there
      //was none at the start.  In either case we do nothing as the previous trimming will've 
      //got rid of the whitespace if case 1
    }
    else{
      trim_to_point(start_position);
    }
  }

  private void changed()
  {
    checked_for_next = false;
  }

  //set the delimiter to whitespace
  public void set_delimiter ()
  {
    delimiter = ' ';
    changed();
    checked_up_to = start;
  }

  //set it to the specified character
  public void set_delimiter (char delimiter)
  {
    this.delimiter = delimiter;
    changed();
    checked_up_to = start;
  }

  public void set_lazy_mode(boolean lazy_mode)
  {
    this.lazy_mode = lazy_mode;
    changed();
    checked_up_to = start;
    if (next_buffer_created){
      next.clear();
    }
  }

  //check if the current string has a next token (with whatever delimiter on both sides)
  //NOTE this could be speeded up by keeping track of what point we have checked up to
  public boolean hasNext()
  {
    if (!next_buffer_created){
      create_next_buffer();
    }
    if (!checked_for_next){
      search_for_next();
    }
    
    checked_for_next = true;

    return hasnext;
  }

  //get the next token and put it into the specified CharString
  public void next(CharString output)
  {
    if (!next_buffer_created){
      create_next_buffer();
    }

    if (!checked_for_next){
      search_for_next ();
    }

    if (!hasnext){
      String message = "Error no next token";
      Exception e = new Exception(message);
      e.printStackTrace();
      System.exit(1);
    }
    trim_to_point(next_end);
    changed();

    output.set(next);
    next.clear();
    checked_up_to = start;
  }

  //get the next token and return it as a string
  public String next()
  {
    if (!next_buffer_created){
      create_next_buffer();
    }

    if (!checked_for_next){
      search_for_next ();
    }

    if (!hasnext){
      String message = "Error no next token";
      NoSuchElementException e = new NoSuchElementException(message);
    }
     
    trim_to_point(next_end);
    changed();
  
    try{
      return next.asString();
    }
    finally{
      next.clear();
      checked_up_to = start;
    }
  }

  private void search_for_next()
  {
    hasnext = false;
    boolean characters_found = false;
    next_start = -1;
    next_end = -1;

    //go through each character in the array
    for (int i = checked_up_to; i < array_usage; i++){
      //if we are using a whitespace delimiter...
      char c = array[i];
      if (delimiter == ' '){
        //check if character is whitespace...
        if (Character.isWhitespace(c)){
          //if it is and characters have already been found...
          if (characters_found){
            //we must now be at the end of a token so break
            next_end = i-1;
            break;
          }
          //otherwise skip as we have no content yet
          else{

          }
        }
        //if the character is not whitespace...
        else{
          //and no characters have been found already...
          if (!characters_found){
            //record the findings
            characters_found = true;
            next_start = i;
          }
          //add the character to the next token
          next.add(c);
        }
      }

      //if delimiter is newline
      else if (delimiter == '\n'){
        //check if character is newline (all different types!)...
        if (c == '\n' || c == '\r' ||
           (i > start && array[i-1] == '\r' && c == '\n')){

          //if it is and characters have already been found...
          if (characters_found){
            //we must now be at the end of a token so break
            next_end = i-1;
            break;
          }
          //otherwise skip as we have no content yet
          else{

          }
        }

        //if the character is not whitespace...
        else{
          //and no characters have been found already...
          if (!characters_found){
            //record the findings
            characters_found = true;
            next_start = i;
          }
          //add the character to the next token
          next.add(c);
        }


      }
      //otherwise just use whatever token has been provided...
      else{
        if (c == delimiter){
          //if it matches and characters have already been found...
          if (characters_found){
            //we must now be at the end of a token so break
            next_end = i-1;
            break;
          }
          //otherwise skip as we have no content yet
          else{

          }
        }
        //if the character doesn't match...
        else{
          //and no characters have been found already...
          if (!characters_found){
            //record the findings
            characters_found = true;
            next_start = i;
          }
          //add the character to the next token
          next.add(c);
        }
      }
    }

    //if start of a token has been found
    if (next_start != -1){
      //if we are in lazy mode...
      if (lazy_mode){
        //declare that we a have next token
        hasnext = true;
        //if there was no end delimiter found (means all content was checked)
        if (next_end == -1){
          //set the end to the end of content (+set checked_up_to_value)
          next_end = array_usage-1;
          checked_up_to = next_end;
        }
        //otherwise we have checked up to the end of the token
        else{
          checked_up_to = next_end;
        }
      }
      //if we're not in lazy mode (eg we want only strict output)
      else {
        //if we have found a delimiter after some content...
        if (next_end != -1){
          //set hasnext to true
          hasnext = true;
          checked_up_to = next_end;
        }
        else{
          checked_up_to = array_usage;
        }
      }
    }
  }

  private void create_next_buffer ()
  {
    next = new CharString ();
    next_buffer_created = true;
  }
}
